import { _decorator, Component, Node } from 'cc';
const { ccclass, property } = _decorator;

type Point = { x: number, y: number };

interface AStarOptions {
    allowDiagonal?: boolean;
    useWeight?: boolean;      // 是否启用权重地图
    useSmoothing?: boolean;   // 是否路径平滑
}

export class AStar {
    private grid: number[][];
    private width: number;
    private height: number;
    private allowDiagonal: boolean;
    private useWeight: boolean;
    private useSmoothing: boolean;

    constructor(grid: number[][], options: AStarOptions = {allowDiagonal:false, useWeight: false, useSmoothing: false}) {
        this.grid = grid;
        this.height = grid.length;
        this.width = grid[0].length;
        this.allowDiagonal = options.allowDiagonal ?? false;
        this.useWeight = options.useWeight ?? false;
        this.useSmoothing = options.useSmoothing ?? false;
    }

    /** 更新地图（支持动态障碍） */
    public updateGrid(grid: number[][]) {
        this.grid = grid;
        this.height = grid.length;
        this.width = grid[0].length;
    }

    private heuristic(a: Point, b: Point): number {
        return Math.abs(a.x - b.x) + Math.abs(a.y - b.y);
    }

    private neighbors(node: Point): Point[] {
        const dirs = this.allowDiagonal
            ? [ [0,1], [1,0], [0,-1], [-1,0], [1,1], [1,-1], [-1,1], [-1,-1] ]
            : [ [0,1], [1,0], [0,-1], [-1,0] ];
        const result: Point[] = [];
        for (const [dx, dy] of dirs) {
            const nx = node.x + dx, ny = node.y + dy;
            if (nx >= 0 && nx < this.width && ny >= 0 && ny < this.height && this.grid[ny][nx] !== 1) {
                result.push({ x: nx, y: ny });
            }
        }
        return result;
    }

    public findPath(start: Point, end: Point): Point[] | null {
        const openSet: Point[] = [start];
        const cameFrom: Map<string, Point> = new Map();
        const gScore: Map<string, number> = new Map();
        const fScore: Map<string, number> = new Map();

        const key = (p: Point) => `${p.x},${p.y}`;
        gScore.set(key(start), 0);
        fScore.set(key(start), this.heuristic(start, end));

        while (openSet.length > 0) {
            openSet.sort((a, b) => (fScore.get(key(a)) ?? Infinity) - (fScore.get(key(b)) ?? Infinity));
            const current = openSet.shift()!;
            if (current.x === end.x && current.y === end.y) {
                let path: Point[] = [current];
                let currKey = key(current);
                while (cameFrom.has(currKey)) {
                    const prev = cameFrom.get(currKey)!;
                    path.push(prev);
                    currKey = key(prev);
                }
                path = path.reverse();
                if (this.useSmoothing) {
                    path = this.smoothPath(path);
                }
                return path;
            }
            for (const neighbor of this.neighbors(current)) {
                // 权重地图支持
                const cost = this.useWeight ? Math.max(1, this.grid[neighbor.y][neighbor.x]) : 1;
                const tentativeG = (gScore.get(key(current)) ?? Infinity) + cost;
                if (tentativeG < (gScore.get(key(neighbor)) ?? Infinity)) {
                    cameFrom.set(key(neighbor), current);
                    gScore.set(key(neighbor), tentativeG);
                    fScore.set(key(neighbor), tentativeG + this.heuristic(neighbor, end));
                    if (!openSet.some(p => p.x === neighbor.x && p.y === neighbor.y)) {
                        openSet.push(neighbor);
                    }
                }
            }
        }
        return null;
    }

    /** 路径平滑（线段可达性检测） */
    private smoothPath(path: Point[]): Point[] {
        if (path.length <= 2) return path;
        const result: Point[] = [path[0]];
        let i = 0;
        while (i < path.length - 1) {
            let j = path.length - 1;
            while (j > i + 1) {
                if (this.canLinePass(path[i], path[j])) break;
                j--;
            }
            result.push(path[j]);
            i = j;
        }
        return result;
    }

    /** 判断两点间直线是否可达（Bresenham算法/采样） */
    private canLinePass(a: Point, b: Point): boolean {
        const dx = Math.abs(b.x - a.x), dy = Math.abs(b.y - a.y);
        const sx = a.x < b.x ? 1 : -1, sy = a.y < b.y ? 1 : -1;
        let err = dx - dy, x = a.x, y = a.y;
        while (!(x === b.x && y === b.y)) {
            if (this.grid[y][x] === 1) return false;
            const e2 = 2 * err;
            if (e2 > -dy) { err -= dy; x += sx; }
            if (e2 < dx) { err += dx; y += sy; }
        }
        return true;
    }

    /** 开关控制 */
    public setUseWeight(flag: boolean) { this.useWeight = flag; }
    public setUseSmoothing(flag: boolean) { this.useSmoothing = flag; }
    public setAllowDiagonal(flag: boolean) { this.allowDiagonal = flag; }
}


